home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / static / regex.c < prev    next >
Text File  |  1996-03-13  |  9KB  |  409 lines
  1. /*
  2.  * Copyright (c) 1980 Regents of the University of California.
  3.  * All rights reserved.  The Berkeley software License Agreement
  4.  * specifies the terms and conditions for redistribution.
  5.  */
  6.  
  7. #if defined(LIBC_SCCS) && !defined(lint)
  8. static char sccsid[] = "@(#)regex.c    5.2 (Berkeley) 3/9/86";
  9. #endif LIBC_SCCS and not lint
  10.  
  11.  
  12. /*
  13.  * routines to do regular expression matching
  14.  *
  15.  * Entry points:
  16.  *
  17.  *    re_comp(s)
  18.  *        char *s;
  19.  *     ... returns 0 if the string s was compiled successfully,
  20.  *             a pointer to an error message otherwise.
  21.  *         If passed 0 or a null string returns without changing
  22.  *           the currently compiled re (see note 11 below).
  23.  *
  24.  *    re_exec(s)
  25.  *        char *s;
  26.  *     ... returns 1 if the string s matches the last compiled regular
  27.  *               expression, 
  28.  *             0 if the string s failed to match the last compiled
  29.  *               regular expression, and
  30.  *            -1 if the compiled regular expression was invalid 
  31.  *               (indicating an internal error).
  32.  *
  33.  * The strings passed to both re_comp and re_exec may have trailing or
  34.  * embedded newline characters; they are terminated by nulls.
  35.  *
  36.  * The identity of the author of these routines is lost in antiquity;
  37.  * this is essentially the same as the re code in the original V6 ed.
  38.  *
  39.  * The regular expressions recognized are described below. This description
  40.  * is essentially the same as that for ed.
  41.  *
  42.  *    A regular expression specifies a set of strings of characters.
  43.  *    A member of this set of strings is said to be matched by
  44.  *    the regular expression.  In the following specification for
  45.  *    regular expressions the word `character' means any character but NUL.
  46.  *
  47.  *    1.  Any character except a special character matches itself.
  48.  *        Special characters are the regular expression delimiter plus
  49.  *        \ [ . and sometimes ^ * $.
  50.  *    2.  A . matches any character.
  51.  *    3.  A \ followed by any character except a digit or ( )
  52.  *        matches that character.
  53.  *    4.  A nonempty string s bracketed [s] (or [^s]) matches any
  54.  *        character in (or not in) s. In s, \ has no special meaning,
  55.  *        and ] may only appear as the first letter. A substring 
  56.  *        a-b, with a and b in ascending ASCII order, stands for
  57.  *        the inclusive range of ASCII characters.
  58.  *    5.  A regular expression of form 1-4 followed by * matches a
  59.  *        sequence of 0 or more matches of the regular expression.
  60.  *    6.  A regular expression, x, of form 1-8, bracketed \(x\)
  61.  *        matches what x matches.
  62.  *    7.  A \ followed by a digit n matches a copy of the string that the
  63.  *        bracketed regular expression beginning with the nth \( matched.
  64.  *    8.  A regular expression of form 1-8, x, followed by a regular
  65.  *        expression of form 1-7, y matches a match for x followed by
  66.  *        a match for y, with the x match being as long as possible
  67.  *        while still permitting a y match.
  68.  *    9.  A regular expression of form 1-8 preceded by ^ (or followed
  69.  *        by $), is constrained to matches that begin at the left
  70.  *        (or end at the right) end of a line.
  71.  *    10. A regular expression of form 1-9 picks out the longest among
  72.  *        the leftmost matches in a line.
  73.  *    11. An empty regular expression stands for a copy of the last
  74.  *        regular expression encountered.
  75.  */
  76.  
  77. /*
  78.  * constants for re's
  79.  */
  80. #define    CBRA    1
  81. #define    CCHR    2
  82. #define    CDOT    4
  83. #define    CCL    6
  84. #define    NCCL    8
  85. #define    CDOL    10
  86. #define    CEOF    11
  87. #define    CKET    12
  88. #define    CBACK    18
  89.  
  90. #define    CSTAR    01
  91.  
  92. #define    ESIZE    512
  93. #define    NBRA    9
  94.  
  95. static    char    expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
  96. static    char    circf;
  97.  
  98. static int advance(register char *, register char *);
  99. int cclass(register char *, register char, int);
  100. int backref(register int, register char *);
  101.  
  102. /*
  103.  * compile the regular expression argument into a dfa
  104.  */
  105. char *
  106. re_comp(sp)
  107.     register char    *sp;
  108. {
  109.     register int    c;
  110.     register char    *ep = expbuf;
  111.     int    cclcnt, numbra = 0;
  112.     char    *lastep = 0;
  113.     char    bracket[NBRA];
  114.     char    *bracketp = &bracket[0];
  115.     static    char    *retoolong = "Regular expression too long";
  116.  
  117. #define    comerr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
  118.  
  119.     if (sp == 0 || *sp == '\0') {
  120.         if (*ep == 0)
  121.             return("No previous regular expression");
  122.         return(0);
  123.     }
  124.     if (*sp == '^') {
  125.         circf = 1;
  126.         sp++;
  127.     }
  128.     else
  129.         circf = 0;
  130.     for (;;) {
  131.         if (ep >= &expbuf[ESIZE])
  132.             comerr(retoolong);
  133.         if ((c = *sp++) == '\0') {
  134.             if (bracketp != bracket)
  135.                 comerr("unmatched \\(");
  136.             *ep++ = CEOF;
  137.             *ep++ = 0;
  138.             return(0);
  139.         }
  140.         if (c != '*')
  141.             lastep = ep;
  142.         switch (c) {
  143.  
  144.         case '.':
  145.             *ep++ = CDOT;
  146.             continue;
  147.  
  148.         case '*':
  149.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
  150.                 goto defchar;
  151.             *lastep |= CSTAR;
  152.             continue;
  153.  
  154.         case '$':
  155.             if (*sp != '\0')
  156.                 goto defchar;
  157.             *ep++ = CDOL;
  158.             continue;
  159.  
  160.         case '[':
  161.             *ep++ = CCL;
  162.             *ep++ = 0;
  163.             cclcnt = 1;
  164.             if ((c = *sp++) == '^') {
  165.                 c = *sp++;
  166.                 ep[-2] = NCCL;
  167.             }
  168.             do {
  169.                 if (c == '\0')
  170.                     comerr("missing ]");
  171.                 if (c == '-' && ep [-1] != 0) {
  172.                     if ((c = *sp++) == ']') {
  173.                         *ep++ = '-';
  174.                         cclcnt++;
  175.                         break;
  176.                     }
  177.                     while (ep[-1] < c) {
  178.                         *ep = ep[-1] + 1;
  179.                         ep++;
  180.                         cclcnt++;
  181.                         if (ep >= &expbuf[ESIZE])
  182.                             comerr(retoolong);
  183.                     }
  184.                 }
  185.                 *ep++ = c;
  186.                 cclcnt++;
  187.                 if (ep >= &expbuf[ESIZE])
  188.                     comerr(retoolong);
  189.             } while ((c = *sp++) != ']');
  190.             lastep[1] = cclcnt;
  191.             continue;
  192.  
  193.         case '\\':
  194.             if ((c = *sp++) == '(') {
  195.                 if (numbra >= NBRA)
  196.                     comerr("too many \\(\\) pairs");
  197.                 *bracketp++ = numbra;
  198.                 *ep++ = CBRA;
  199.                 *ep++ = numbra++;
  200.                 continue;
  201.             }
  202.             if (c == ')') {
  203.                 if (bracketp <= bracket)
  204.                     comerr("unmatched \\)");
  205.                 *ep++ = CKET;
  206.                 *ep++ = *--bracketp;
  207.                 continue;
  208.             }
  209.             if (c >= '1' && c < ('1' + NBRA)) {
  210.                 *ep++ = CBACK;
  211.                 *ep++ = c - '1';
  212.                 continue;
  213.             }
  214.             *ep++ = CCHR;
  215.             *ep++ = c;
  216.             continue;
  217.  
  218.         defchar:
  219.         default:
  220.             *ep++ = CCHR;
  221.             *ep++ = c;
  222.         }
  223.     }
  224. }
  225.  
  226. /* 
  227.  * match the argument string against the compiled re
  228.  */
  229. int
  230. re_exec(p1)
  231.     register char    *p1;
  232. {
  233.     register char    *p2 = expbuf;
  234.     register int    c;
  235.     int    rv;
  236.  
  237.     for (c = 0; c < NBRA; c++) {
  238.         braslist[c] = 0;
  239.         braelist[c] = 0;
  240.     }
  241.     if (circf)
  242.         return((advance(p1, p2)));
  243.     /*
  244.      * fast check for first character
  245.      */
  246.     if (*p2 == CCHR) {
  247.         c = p2[1];
  248.         do {
  249.             if (*p1 != c)
  250.                 continue;
  251.                         rv = advance(p1, p2);
  252.                         if (rv)
  253.                 return(rv);
  254.         } while (*p1++);
  255.         return(0);
  256.     }
  257.     /*
  258.      * regular algorithm
  259.      */
  260.     do
  261.                 if ((rv = advance(p1, p2)))
  262.             return(rv);
  263.     while (*p1++);
  264.     return(0);
  265. }
  266.  
  267. /* 
  268.  * try to match the next thing in the dfa
  269.  */
  270. static    int
  271. advance(lp, ep)
  272.     register char    *lp, *ep;
  273. {
  274.     register char    *curlp;
  275.     int    ct, i;
  276.     int    rv;
  277.  
  278.     for (;;)
  279.         switch (*ep++) {
  280.  
  281.         case CCHR:
  282.             if (*ep++ == *lp++)
  283.                 continue;
  284.             return(0);
  285.  
  286.         case CDOT:
  287.             if (*lp++)
  288.                 continue;
  289.             return(0);
  290.  
  291.         case CDOL:
  292.             if (*lp == '\0')
  293.                 continue;
  294.             return(0);
  295.  
  296.         case CEOF:
  297.             return(1);
  298.  
  299.         case CCL:
  300.             if (cclass(ep, *lp++, 1)) {
  301.                 ep += *ep;
  302.                 continue;
  303.             }
  304.             return(0);
  305.  
  306.         case NCCL:
  307.             if (cclass(ep, *lp++, 0)) {
  308.                 ep += *ep;
  309.                 continue;
  310.             }
  311.             return(0);
  312.  
  313.         case CBRA:
  314.                         braslist[(int)*ep++] = lp;
  315.             continue;
  316.  
  317.         case CKET:
  318.                         braelist[(int)*ep++] = lp;
  319.             continue;
  320.  
  321.         case CBACK:
  322.             if (braelist[i = *ep++] == 0)
  323.                 return(-1);
  324.             if (backref(i, lp)) {
  325.                 lp += braelist[i] - braslist[i];
  326.                 continue;
  327.             }
  328.             return(0);
  329.  
  330.         case CBACK|CSTAR:
  331.             if (braelist[i = *ep++] == 0)
  332.                 return(-1);
  333.             curlp = lp;
  334.             ct = braelist[i] - braslist[i];
  335.             while (backref(i, lp))
  336.                 lp += ct;
  337.             while (lp >= curlp) {
  338.                                 rv = advance(lp, ep);
  339.                                 if (rv)
  340.                     return(rv);
  341.                 lp -= ct;
  342.             }
  343.             continue;
  344.  
  345.         case CDOT|CSTAR:
  346.             curlp = lp;
  347.             while (*lp++)
  348.                 ;
  349.             goto star;
  350.  
  351.         case CCHR|CSTAR:
  352.             curlp = lp;
  353.             while (*lp++ == *ep)
  354.                 ;
  355.             ep++;
  356.             goto star;
  357.  
  358.         case CCL|CSTAR:
  359.         case NCCL|CSTAR:
  360.             curlp = lp;
  361.             while (cclass(ep, *lp++, ep[-1] == (CCL|CSTAR)))
  362.                 ;
  363.             ep += *ep;
  364.             goto star;
  365.  
  366.         star:
  367.             do {
  368.                 lp--;
  369.                                 rv = advance(lp, ep);
  370.                                 if (rv)
  371.                     return(rv);
  372.             } while (lp > curlp);
  373.             return(0);
  374.  
  375.         default:
  376.             return(-1);
  377.         }
  378. }
  379.  
  380. int
  381. backref(i, lp)
  382.     register int    i;
  383.     register char    *lp;
  384. {
  385.     register char    *bp;
  386.  
  387.     bp = braslist[i];
  388.     while (*bp++ == *lp++)
  389.         if (bp >= braelist[i])
  390.             return(1);
  391.     return(0);
  392. }
  393.  
  394. int
  395. cclass(set, c, af)
  396.     register char    *set, c;
  397.     int    af;
  398. {
  399.     register int    n;
  400.  
  401.     if (c == 0)
  402.         return(0);
  403.     n = *set++;
  404.     while (--n)
  405.         if (*set++ == c)
  406.             return(af);
  407.     return(! af);
  408. }
  409.